#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

vector<int> getLeastNumbers(vector<int>& arr, int k) {
    priority_queue<int> pq;
    for (int i = 0; i < k; i++)
    {
        pq.push(arr[i]);
    }

    for (int i = k; i < arr.size(); i++)
    {
        int top = pq.top();
        if (top > arr[i])
        {
            pq.pop();
            pq.push(arr[i]);
        }
    }
    vector<int> res;
    while (!pq.empty())
    {
        int top = pq.top();
        pq.pop();
        res.push_back(top);
    }
    return res;
}

int main()
{
    vector<int> v = { 3,2,1 };
    getLeastNumbers(v, 2);
    return 0;
}

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {}

    void addNum(int num) {
        if (qmin.empty() || num < qmin.top())
        {
            qmin.push(num);
            if (qmin.size() > qmax.size() + 1)
            {
                qmax.push(qmin.top());
                qmin.pop();
            }
        }
        else
        {
            qmax.push(num);
            if (qmin.size() < qmax.size())
            {
                qmin.push(qmax.top());
                qmax.pop();
            }
        }
    }

    double findMedian() {
        if (qmin.size() > qmax.size())
            return qmin.top();

        return (qmin.top() + qmax.top()) / 2.0;
    }
private:
    priority_queue<int> qmin;
    priority_queue<int, vector<int>, greater<int>> qmax;
};
